package com.mlh.dp.old;

// 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
// 请你返回让 s 成为回文串的 最少操作次数 。
// 「回文串」是正读和反读都相同的字符串。
//
// 输入：s = "zzazz"
// 输出：0
// 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。


public class MinInsertions {

    //这些困难题其实解法都是由基本解法来解决的  但是他不会让你简单看出来是用那个算法可以做出来
    //难点就在于题目的变形，看你能不能变形成依靠基础解法为支撑的题目
    //那这题来说  这题一开始我也没想出变形
    //换个角度想:当前字符串要变成回文,那只要把不一样的找出来就好了.即:求出反过来的字符串和当前字符串的最长公共子序列,然后减一下.
    //这题目如果能这样变形出来  那就很简单了
    //还有注意子串和子序列的差别
    public static int method1(String s){
        int n=s.length();
        char[]s1=s.toCharArray();
        char[]s2=new char[n];
        int a=0;
        for(char temp:s1){
            s2[a]=s1[n-1-a];
            a++;
        }
        int[][]dp=new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return n-dp[n][n];
    }

    //优化了方式1的需要额外char数组
    public static int method2(String s){
        int n=s.length();
        char[]s1=s.toCharArray();
        int[][]dp=new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s1[n-j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return n-dp[n][n];
    }

}
